package com.dkd.day20250817;

import java.util.Scanner;

public class test1 {
    //题目描述
    //疫情期间，有一批社区的家庭需要配送爱心蔬菜，每个社区的家庭个数用communities数组表示
    // （下标表示社区编号，值表示对应社区的家庭个数，例如：communities[0]=5 表示第0个社区有5个家庭）。
    //
    //现有 num 个志愿者为这些社区家庭配送蔬菜，配送规则如下：
    //
    //每个社区只能安排 1 个志愿人员进行配送。
    //每个志愿者只能被分配一次任务，配送编号连续的若干个社区，例如：第k个志愿者可以配送communities[0]、communities[1]、
    // communities[2]、communities[3]，但不能配送communities[0]、communities[3]、communities[4]。
    //为每个家庭配送爱心蔬菜耗时均为1小时。
    //志愿者可并行配送。
    //请合理分配志愿者, 使得能够在最短的时间内完成配送任务，并返回所需的小时数。
    //
    //解答要求
    //时间限制：1000ms, 内存限制：256MB
    //输入
    //第一行表示志愿者数 num，取值范围为 [1,10^5]
    //第二行表示 communities 数组的长度（即社区数），取值范围为 [1,10^5]
    //第三行表示 communities 数组，表示各社区的家庭数，数组元素的取值范围为 [1,10^4]
    //
    //输出
    //一个整数，表示完成配送任务最少需要的小时数
    //
    //样例
    //输入样例 1
    //
    //2
    //3
    //40 10 20
    //输出样例 1
    //
    //40
    //提示样例 1
    //两个人并行配送：一人负责社区0，需要40小时；另外一人负责社区1和2，需要30个小时。因此最少需要40小时。
    //
    //
    //
    //输入样例 2
    //
    //2
    //4
    //1 1 6 2
    //输出样例 2
    //
    //8
    //提示样例 2
    //两人并行：
    //方案1：一人配送 1 + 1 + 6 , 另一人配送 2，完成需要8小时
    //方案2：一人配送 1 + 1，另一人配送 6 + 2，完成需要8小时
    //两种方案，完成配送最短时间都是 8；其它方案的配送时间都更长；因此返回 8
    //
    //
    //
    //输入样例 3
    //
    //3
    //2
    //1 2
    //输出样例 3
    //
    //2
    //提示样例 3
    //因为每个社区只能分配一名志愿者，所以2个社区只能分配2个志愿者，共需要2个小时
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int volunteer = sc.nextInt();
        int n = sc.nextInt();
        int [] communities = new int[n];
        for (int i = 0; i < n; i++) {
            communities[i] = sc.nextInt();
        }

        System.out.println(solve(volunteer, communities));

    }

    public static int solve( int volunteerNum,int[] communities){
        long totalTime = 0L;
        int maxTime = 0;
        for(int community : communities){
            totalTime += community;
            maxTime = Math.max(maxTime,community);
        }

        long left  = maxTime;
        long right = totalTime;

        long minTime = right;
        while(left <= right){
            long midTime = left + (right-left)/2;

            if(canFinish(midTime,volunteerNum,communities)){
                minTime = midTime;
                right = midTime-1;
            }else {
                left = midTime+1;
            }
        }

        return (int)minTime;
    }

    public static boolean canFinish(Long timeLimit,int volunteerNum,int[] communities){
        int volunteerNum1 = 1;
        int communitySum = 0;
        for(int community : communities){
            if(community > timeLimit){
                return false;
            }
            if(communitySum +community <= timeLimit){
                communitySum += community;
            }else{
                volunteerNum1++;
                communitySum = community;
            }

        }
        return volunteerNum1 <= volunteerNum;
    }
}
